#include<stdio.h>
#include<stdlib.h>

typedef struct btnode{
	char data;
	struct btnode* lchild;
	struct btnode* rchild;
} BtNode;

// 先序遍历 二叉树
void prior_order(BtNode *tree){
	if(tree){ //空节点直接跳过
		printf("%c >", tree->data);
		prior_order( tree->lchild );
		prior_order( tree->rchild );
	}
}

// 中序遍历 二叉树
void in_order(BtNode *tree){
	if(tree){ //空节点直接跳过
		in_order( tree->lchild );
		printf("%c >", tree->data);
		in_order( tree->rchild );
	}
}

// 后序遍历 二叉树
void post_order(BtNode *tree){
	if(tree){ //空节点直接跳过
		post_order( tree->lchild );
		post_order( tree->rchild );
		printf("%c >", tree->data);
	}
}

//二叉树的创建可以使用递归方法
void create(BtNode **node){
	printf("逐个输入字符，递归生成二叉树\n");
	char ch;
	scanf("%c", &ch);
	getchar(); //吃掉回车键
	
	if(ch=='/')
		return;
	*node = ( BtNode* )malloc( sizeof(BtNode) );
	
	(*node)->data=ch;
	printf("data: %c\n", (*node)->data );
	
	(*node)->lchild=NULL;
	(*node)->rchild=NULL;
	
	create( &(*node)->lchild);
	create( &(*node)->rchild);
}

void deltree(BtNode * tree) {
    if(tree) {
        deltree(tree->lchild);
        deltree(tree->rchild);
        free(tree);
    }
}

//打印二叉树
void printTree(BtNode* root, int depth, char* prefix) {
    if (root == NULL) return;
    
    // 打印当前节点前的基础缩进
    for (int i = 1; i < depth; i++) {
        //printf("%s", (i == depth-1) ? "│  " : "   ");
        printf("%s", "│  ");
    }
    // 打印当前节点的值
    printf("%s%c\n", prefix, root->data);

    // 递归打印子节点
    if (root->lchild || root->rchild) {
        printTree(root->lchild, depth + 1, "├──L:");
        printTree(root->rchild, depth + 1, "└──R:");
    }
}

int main(){
	BtNode *p; 
	create(&p); 
/*
# 1.demo1
      a
    /    \
   b      c
  /  \    /  \
 d   e   f   /
输入: a b d / / e / / c f / / /
打印效果：
a
├──L:b
│  ├──L:d
│  └──R:e
└──R:c
│  ├──L:f


# 2.demo2
      a
    /    \
   b      c
  /  \    /  \
 d   e   f   /
g h  /\  /i
输入: a b d g / / h / / e / / c f / i / / /
打印效果：相当于拿着左下角掂起来，沾到右上角墙上，其余自然下垂后，恢复原二叉树效果。
a
├──L:b
│  ├──L:d
│  │  ├──L:g
│  │  └──R:h
│  └──R:e
└──R:c
│  ├──L:f
│  │  └──R:i
*/

	prior_order(p);
	printf("\n");

	in_order(p);
	printf("\n");

	post_order(p);
	printf("\n");

    //打印树结构: 
    printTree(p, 0, "");

	deltree(p);
	return 0;
}
